1. Field of the Invention
This invention relates generally to a technique for preventing starving threads in a counting semaphore and, more particularly, to a technique for preventing starving threads in a counting semaphore that includes allowing threads to steal resources from waiting threads until a thread becomes starved.
2. Discussion of the Related Art
Multi-tasking computer operating systems (OS), such as the UNIX operating system, typically employ process algorithms at the kernel level that are referred to as threads. A thread is a portion of code having an object of activity and includes a program counter, a process stack and a set of processor registers. The thread is executed when it receives a command to run the portion of code. The thread needs a central processing unit (CPU) and typically needs a resource, such as a table entry or other data, to execute. A thread is starved if it has been commanded to execute and is waiting for a CPU to become available, but is prevented from executing for an unreasonable period of time or indefinitely because when the CPU becomes available, the resource is not available to the thread because it is being used by another thread executing another portion of code. One or more starving threads could affect system performance, and may prevent other threads from executing that need the starving thread to first execute.
Operating systems of this type also employ locks. A lock is a portion of code that locks resources when the resources are being used by a thread. The thread using the resource locks the lock by decrementing a counter to zero to prevent more than one thread from using the resource. When the thread is done using the resource, the counter is incremented and the lock is unlocked. Thus, the lock prevents multiple threads from simultaneously using the same resource.
A counting semaphore is a sleeping lock that puts a thread into a wait queue until a resource needed by the thread becomes available. Counting semaphores are blocking primitives that are primarily used in a producer/consumer environment. For example, if five resources are available to be used by the threads, each time a thread uses one or more of the resources, the counting semaphore decrements a count indicating that a fewer number of the resources are currently available for other threads. When a thread returns the resource, the counting semaphore increments the count indicating that the resource is now available. If decrementing the count would cause it to go negative, the thread will be blocked or put to sleep on the wait queue until a resource becomes available.
If a resource becomes available to the sleeping thread at the front of the wait queue, the thread is woken up to use the resource. However, depending on what type of thread has been woken up, such as a high priority or low priority thread, a CPU may not be currently available for that thread to execute its code and use the resource. Some algorithms allow new threads that arrive at the semaphore to take available resources so that the resources are being used as much as possible to increase system performance. As mentioned above, when the thread that has been woken up and is waiting for the CPU does get the CPU, resources may not then be available. The woken thread is sent to the end of the queue and put back to sleep. Such a process could cause a starving thread where the thread may never execute, possibly reducing system performance. In this system, there is thus no guarantee that the thread will ever satisfy its request. Thread starvation becomes very complicated when threads decrement the counting semaphore by a large value.
In one known programming technique that avoids starving threads in a counting semaphore, the algorithm “reserves” resources for threads waiting to execute. In other words, a thread that has been woken up because a resource becomes available has that resource reserved for it by immediately decrementing the counter until a CPU becomes available and the thread will actually use the resource. This is a first in-first out (FIFO) operation, where all the sleeping threads in the wait queue will eventually obtain the resource when they are moved to the front of the queue and are woken. However, this reduces system performance because valuable resources may be unused when needed because a thread is holding the resource without using it.
It would be desirable to address both the performance and starvation issues discussed above in a counting semaphore.